package com.mdnote.algorithm;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/9/6
 * @description 二分查找 非递归
 */
public class BinarySearch {


    /**
     * 二分查找
     * @param arr 数组
     * @param targetValue 目标元素
     * @return 目标元素索引
     */
    public int search(int[] arr, int targetValue) {

        int leftCursor = 0;
        int rightCursor = arr.length - 1;

        while (leftCursor <= rightCursor) {
            int mid = (leftCursor + rightCursor) / 2;
            if (arr[mid] == targetValue) {
                // 找到了
                return mid;
            }
            if (targetValue < arr[mid]) {
                // 向左搜索
                rightCursor = mid - 1;
            } else {
                leftCursor = mid + 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {11, 22, 44, 55, 66, 77};
        BinarySearch binarySearch = new BinarySearch();
        int index = binarySearch.search(arr, 22);
        System.out.println(index);
    }
}
